1. Field of the Invention
The present invention relates to a system for speeding up the arithmetic coding processing and method thereof, and more particularly, to a system used in the JBIG (Joint Bi-level Image Experts Group) for compressing a bi-level image data and method thereof.
2. Related Art
In the present society with universal information flow, as the quantity demanded for images is becoming larger and larger, the digitization of images is a necessary trend. However, the digitized image has a great amount of data and occupies too much memory, such that it takes a lot of time in data transmission and processing, and is also inconvenient. It is a perfect solution to compress the data.
The image data compression techniques have a wide application foreground. It can be said that, all the digital image products are involved in the image data compression techniques, and the digitization of the electronic products is the general trend. For example, high-definition digital televisions will replace the analog televisions, video telephones will replace the traditional voice telephones, and digital cameras will replace the film cameras, and so on.
The invention and wide use of the facsimile technology promote the quick development of the bi-level image compression algorithm. CCITT (Consultative Committee for International Telegraph and Telephone, an institution of the International Telecommunication Union (ITU)) establishes a series of image compression standards for the fax-like applications, exclusively- used in compressing and delivering bi-level images. These standards substantially include CCITT Group 1 and Group 2 in the late 1970s, CCITT Group 3 in 1980 and CCITT Group 4 in 1984. The JBIG (Joint Bi-level Image Experts Group) founded by CCITT and ISO (International Organization for Standardization) together in 1993 further develop the bi-level image compression to the lossless compression of a black-and-white image file, such that it becomes a more universal JBIG standard.
Around 1968, P. Elias developed the Shannon-Fano coding method, constructing a much perfect Shannon-Fano-Elias coding from the mathematical view. Along the idea of such an encoding method, in 1976, J. Rissanen proposed an encoding method—arithmetic coding, which may successively approach the information entropy limit. In 1982, Rissanen and G. G. Langdon improved the arithmetic coding. Thereafter, the arithmetic coding was combined with the Prediction by Partial Matching (PPM) model proposed by J. G. Cleary and I. H. Witten in 1984.
The arithmetic coding plays an important role in the JBIG coding compression method. The output of the arithmetic coding is a real number between 0 and 1 by which the decoding terminal may uniquely decode back the original message. Before encoding, the probability of occurrence for each symbol in the message should be calculated at first.
For the lossless compression, the combination of the PPM model and the arithmetic coding may have approached to the information entropy limit to the greatest extent. Unfortunately, the arithmetic coding may obtain the shortest coding length, but the complexity per se and many floating point operations are unfavorable for the hardware implementation, and also make the arithmetic coding slow in operating. Even today with rapid change of development in the speed of the central processing unit (CPU), the operating speed of arithmetic coding programs is difficult to meet the requirements of daily applications.